package leetcode_800;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *SlidingPuzzle_773_ 类似华容道游戏 一个二维数组里只能移动0  问最短多少步移动到目标状态
 *describe:广度优先搜索 对二维数组编码变成字符串 AC 30%
 *2018年10月20日 上午9:21:46
 */
public class SlidingPuzzle_773_ {
	public int slidingPuzzle(int[][] board) {
        Set<String> seen = new HashSet<>();
        String target = "123450";
        //对原二维数组编码 变成字符串
        String s = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
        Queue<String> q = new LinkedList<>(Arrays.asList(s));//使用广度优先搜索算法
        int ans = 0;
        int[] d = { 1, -1, 3, -3 };//有四个方向的移动可能

        seen.add(s); //去重 如果遇到了重复走到此状态  这种走法肯定不是最优解
        while (!q.isEmpty()) {
            for(int sz = q.size(); sz > 0; --sz){ 
                String str = q.poll();
                if (str.equals(target))     return ans; 
                int i = str.indexOf('0');
                for(int k = 0; k < 4; ++k){
                    int j = i + d[k];
                    if (j < 0 || j > 5 || i == 2 && j == 3 || i == 3 && j == 2)     continue;
                    char[] ch = str.toCharArray();
                    char tmp = ch[i];
                    ch[i] = ch[j];
                    ch[j] = tmp;
                    s = String.valueOf(ch);
                    if(seen.add(s))        q.offer(s);
                }
            }
            ++ans;
        }

        return -1;
    }
}
